#include <stdio.h>
#include <stdlib.h>

typedef struct Linked_List *List;
struct Linked_List {
    int Addr;
    int Data;
    int Next_Addr;
    List Next;
};
int first_Addr,N, Reverse;//global variables
List ReadList();
void Attach(int Addr, int Data, int Next_Addr, List *pRear);
List SortList(List L);
void DelteNode(List *pRear);
List ReveredList(List L);
void PrintList(List L);
void FindKth_Modify_Addr(int RF, int K, List L);
List FindKth(int K, List L);
int main()
{
    List Original_list, Sorted_list, Reversed_list;
    Original_list = ReadList();
    if(N!=1)
    {
        Sorted_list = SortList(Original_list);
        Reversed_list = ReveredList(Sorted_list);
    }
    else
    {
        Reversed_list = Original_list;
    }
    PrintList(Reversed_list);
    return 0;
}

List ReadList()
{
    List L, Rear, t;
    int Addr, Data, Next_Addr;
    L = (List)malloc(sizeof(struct Linked_List));
    L->Next = NULL;
    Rear = L;

    scanf("%d %d %d", &first_Addr, &N, &Reverse);
    for (int i = N; i > 0;i--)
    {
        scanf("%d %d %d", &Addr, &Data, &Next_Addr);
        Attach(Addr, Data, Next_Addr, &Rear);
    }

    /* ---- 删除临时生成的头结点 ---- */
    t = L;//为什么这里需要出现t=P呢，如果没有的话 P = P->link直接指向不可以吗？
    L = L->Next;
    free(t);
    /* ---- 删除临时生成的头结点 ---- */
    
    return L;
}

void Attach(int Addr, int Data, int Next_Addr, List *pRear)
{
    List L;
    L = (List)malloc(sizeof(struct Linked_List));
    L->Addr = Addr;
    L->Data = Data;
    L->Next_Addr = Next_Addr;
    L->Next = NULL;
    (*pRear)->Next = L;
    (*pRear) = L;
}

List SortList(List L)
{
    List sorted_L,Rear,move_L,sortedL_Rear,fo_Rear,t;
    int for_num;
    sorted_L=(List)malloc(sizeof(struct Linked_List));
    sortedL_Rear = sorted_L;
    Rear = L;
    while(Rear!=NULL && Rear->Addr != first_Addr)
    {
        fo_Rear = Rear;
        Rear = Rear->Next;
    }
    if(Rear->Addr == first_Addr)
    {
        Attach(Rear->Addr, Rear->Data, Rear->Next_Addr, &sortedL_Rear);
        DelteNode(&fo_Rear);
        for_num = N - 1;
        Rear = L;
        N = 1;
    }
    for (int i = for_num; i > 0;i--)
    {
        for (int j = for_num; j > 0;j--)
        {
            if(Rear->Addr == sortedL_Rear->Next_Addr)
            {
                Attach(Rear->Addr, Rear->Data, Rear->Next_Addr, &sortedL_Rear);
                N++;
                break;
            }
            Rear = Rear->Next;
        }
        Rear = L;
    }

    /* ---- 删除临时生成的头结点 ---- */
    t = sorted_L;//为什么这里需要出现t=P呢，如果没有的话 P = P->link直接指向不可以吗？
    sorted_L = sorted_L->Next;
    free(t);
    /* ---- 删除临时生成的头结点 ---- */
    return sorted_L;
}
void DelteNode(List *pRear)
{
    List s;
    s = (*pRear)->Next;
    (*pRear)->Next = s->Next;
    free(s);
}

List ReveredList(List L)
{
    List Reversed_L;
    int RFromN = N / Reverse;
    int j = RFromN;
    int i = j * Reverse;
    if(Reverse == 1)
    {
        Reversed_L = L;
    }
    else
    {
        for (; j > 0;j--)
        {
            for (; i > (j - 1) * Reverse; i--)
            {
                FindKth_Modify_Addr(j, i, L);
            }
        }
        Reversed_L = SortList(L);
    }
    return Reversed_L;
}

void FindKth_Modify_Addr(int RFj, int K, List L)
{
    int RFromN = N / Reverse;
    List p = L,fo_p;
    int i = 1;
    while(p!=NULL && i<K)
    {
        fo_p = p;
        p = p->Next;
        i++;
    }
    if(i==K)
    {
        if(RFj != RFromN && i%Reverse == 1)
        {
            p->Next_Addr = FindKth((RFj+1)*Reverse, L)->Addr;
        }
        else if(Reverse == N && i == 1)
        {
            p->Next_Addr = -1;
        }
        else if(RFj == RFromN && i == 1)
        {
            p->Next_Addr = FindKth(Reverse, L)->Next->Addr;
        }
        else if(i == Reverse)
        {
            first_Addr = p->Addr;
            p->Next_Addr = fo_p->Addr;
        }
        else if(Reverse * RFromN == N && i == ((RFromN-1)*Reverse +1))
        {
            p->Next_Addr = -1;
        }
        else
        {
            p->Next_Addr = fo_p->Addr;
        }
    }
    else
    {
        printf("ERROR");
    }
}

void PrintList(List L)
{
    List p = L;
    while(p!=NULL)
    {
        if(p->Next_Addr == -1)
        {
            printf("%05d %d %d\n", p->Addr, p->Data, p->Next_Addr);
        }
        else
            printf("%05d %d %05d\n", p->Addr, p->Data, p->Next_Addr);
        p = p->Next;
    }
}

List FindKth(int K, List L)
{
    List p = L;
    int i = 1;
    while(p!=NULL && i<K)
    {
        p = p->Next;
        i++;
    }
    if(i==K)
        return p;
    else
        return NULL;
}